package algorithms;

import java.util.Arrays;

/**
 * 插入排序
 * 算法主要思想（升序）
 * 1.将指定元素插入到已排序好的序列中进行比较
 * 2.比较后大的元素后移，再从后一个元素拿来进行比较
 *
 * 时间复杂度：O(n2)  两层循环
 * 空间复杂度：O(1)没有使用大量辅助空间
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 7, 2, 10, 4};
        System.out.println("排序前：\n" + Arrays.toString(arr));
        int[] sort = InsertionSort.sort(arr);
        System.out.println("排序后：");
        for (int i = 0; i < sort.length; i++) {
        System.out.print(arr[i] + " ");
        }
    }

    static int[] sort(int[] arr) {
        //排序次数
        for (int i = 1; i < arr.length; i++) {
            //前一个元素
            int k = i - 1;
            int end = arr[i];//end代表当前需要插入的元素
            //用后一个元素进行比较,如果小于前一个数，往前移。
            // 寻找要插入的位置
            while (k >= 0 && end < arr[k]) {
                //前一个往后推
                arr[k + 1] = arr[k];
                k--;
            }
            //如果跳出循环，则确认需要插入下标
            arr[k + 1] = end;
        }
        return arr;
    }
}
